---
id: 栈和队列
title: 栈和队列
---

## 栈(stack)

栈是一种线性数据结构，栈中的元素只能先入后出(First In Last Out，简称 FILO)。最早进入的元素存放的位置叫作栈底(bottom)，最后进入的元素存放的位置叫作栈顶 (top)。

#### 栈的应用

栈的输出顺序和输入顺序相反，所以栈通常用于对“历史”的回溯，也就是逆流而上追溯“历史”。
例如实现递归的逻辑，就可以用栈来代替，因为栈可以回溯方法的调用链。

栈还有一个著名的应用场景是面包屑导航，使用户在浏览页面时可以轻松地回
溯到上一级或更上一级页面。

## 队列(queue)

队列(queue)是一种线性数据结构，可以把它想象成排队的场景。 不同于栈的先入后出，队列中的元素只能先入先出(First In First Out，简称 FIFO)。队列的出口端叫作队头(front)，队列的入口端叫作队尾(rear)。

### 队列(实现代码)

- javascript 版

```js
// # 采 用 List 来 容 纳 Queue的数据项
// # 将List首端作为队列 尾端
// # List的末端作为队列 首端
// # enqueue()复杂度为 O(n)
// # dequeue()复杂度为 O(1)

class Queue {
  constructor() {
    this.item = [];
  }

  isEmpty() {
    return this.item.length === 0;
  }

  enqueue(item) {
    this.item.unshift(item);
  }

  dequeue() {
    return this.item.pop();
  }

  size() {
    return this.length;
  }
}

q = new Queue();
console.log(q.item);
console.log(q.isEmpty());
console.log(q.enqueue(3));
console.log(q.enqueue(4));
console.log(q.item);
console.log(q.dequeue());
console.log(q.item);
console.log(q.size());
```

- python 版

```python

# 采 用 List 来 容 纳 Queue的数据项
# 将List首端作为队列 尾端
# List的末端作为队列 首端
# enqueue()复杂度为 O(n)
# dequeue()复杂度为 O(1)

class Queue:
    def __init__(self):
        self.item = []

    def isEmpty(self):
        return self.item == []

    def enqueue(self, item):
        self.item.insert(0, item)

    def dequeue(self):
        return self.item.pop()

    def size(self):
        return len(self.item)

q = Queue();
print(q.isEmpty())
print(q.enqueue(3))
print(q.enqueue(4))
print(q.item)
print(q.size())
print(q.dequeue())
print(q.size())

```

### 队列的应用

队列的输出顺序和输入顺序相同，所以队列通常用于对“历史”的回放，也就是按照“历史”顺序，把“历史”重演一遍。

- 应用场景

  - 例如在多线程中，争夺公平锁的等待队列，就是按照访问顺序来决定线程在队列中的次序的。
  - 再如网络爬虫实现网站抓取时，也是把待抓取的网站 URL 存入队列中，再按照存 入队列的顺序来依次抓取和解析的。

- 应用： 热土豆问题（约瑟夫问题）

```python
# python
# 问题描述：传烫手的热土豆，鼓声停的时候，手里有 土豆的小孩就要出列

# 算法描述：
# 模拟程序采用队列来存放所有参加游戏的人名， 按照传递土豆方向从队首排到队尾。
# 游戏时，队首始终是持有土豆的人
# 模拟游戏开始，只需要将队首的人出队，随即再 到队尾入队，算是土豆的一次传递。
# 传递了num次后，将队首的人移除，不再入队 如此反复，直到队列中剩余1人

class Queue:
    def __init__(self):
        self.item = []

    def isEmpty(self):
        return self.item == []

    def enqueue(self, item):
        self.item.insert(0, item)

    def dequeue(self):
        return self.item.pop()

    def size(self):
        return len(self.item)


def hotPotato(nameList, num):
    simqueue = Queue()
    for name in nameList:
        simqueue.enqueue(name) # 加入队列

    while simqueue.size() > 1:
        for i in range(num):
            if i == num-1:
                simqueue.dequeue()
                break
            dequeue = simqueue.dequeue()
            simqueue.enqueue(dequeue)

    return simqueue.dequeue()

print(hotPotato(['轩', '张', '刘', '蒋','顾','梁','宋','王'], 3))

```

## 双端队列

那么有没有办法把栈和队列的特点结合起来，既可以先入先出，也可以先入后出呢?还真有，这种数据结构叫作双端队列(deque)。

### 双端队列(实现代码)

- javascript 版

```javascript
class Deque {
  constructor() {
    this.item = [];
  }
  isEmpty() {
    return this.item.length == [];
  }

  addFront(item) {
    this.item.push(item);
  }

  addRear(item) {
    this.item.unshift(item);
  }

  removeFront() {
    return this.item.pop();
  }

  removeRear() {
    return this.item.shift();
  }

  size() {
    return this.item.length;
  }
}
```

- python 版

```python

class Deque:
    def __init__(self):
        self.item = []

    def isEmpty(self):
        return self.item == []

    def addFront(self, item):
        self.item.append(item)

    def addRear(self, item):
        return self.item.insert(0,item)

    def removeFront(self):
        return self.item.pop()

    def removeRear(self):
        return self.item.pop(0)

    def size(self):
        return len(self.item)

q = Deque();
print(q.isEmpty())
print(q.addFront(3))
print(q.addFront(4))
print(q.addRear(1))
print(q.addRear(2))
print(q.item)
print(q.removeFront())
print(q.removeRear())
print(q.item)

```

### 双端队列的应用

- 回文词判断

  - 中文：上海自来水来自海上、山东落花生花落东山
  - 英文：radar、madam、toot

- javascript 版

```javascript
class Deque {
  constructor() {
    this.item = [];
  }
  isEmpty() {
    return this.item.length == [];
  }

  addFront(item) {
    this.item.push(item);
  }

  addRear(item) {
    this.item.unshift(item);
  }

  removeFront() {
    return this.item.pop();
  }

  removeRear() {
    return this.item.shift();
  }

  size() {
    return this.item.length;
  }
}

function pelchecker(str) {
  let charDeque = new Deque();
  for (s of str) {
    charDeque.addRear(s);
  }

  let stillEqual = true;
  while (charDeque.size() > 1 && stillEqual) {
    let first = charDeque.removeFront();
    let last = charDeque.removeRear();
    if (first != last) stillEqual = false;
  }
  return stillEqual;
}

console.log(pelchecker("上海自来水来自海上"));
```
- python 版
```python
# 算法描述：
#  1.先将需要判定的词从队尾加入deque。
#  2.再从两端同时移除字符判定是否相同，直到 deque中剩下0个或1个字符。


class Deque:
    def __init__(self):
        self.item = []

    def isEmpty(self):
        return self.item == []

    def addFront(self, item):
        self.item.append(item)

    def addRear(self, item):
        self.item.insert(0,item)

    def removeFront(self):
        return self.item.pop()

    def removeRear(self):
        return self.item.pop(0)

    def size(self):
        return len(self.item)

def pelchecker(str):
    charDeque = Deque()

    for s in str:
        charDeque.addRear(s)

    stillEqual = True

    while charDeque.size() > 1 and stillEqual:
        first = charDeque.removeFront()
        last = charDeque.removeRear()
        if first != last:
            stillEqual = False

    return stillEqual

print(pelchecker('上海自来水来自海上'))
```

## 优先队列(非线性)

还有一种队列，它遵循的不是先入先出，而是谁的优先级最高，谁先出队。
优先队列已经不属于线性数据结构的范畴了，它是基于二叉堆来实现的。关于
优先队列的原理和使用情况，我们会在下一章进行详细介绍。


## 复杂度分析

### 队列 
- enqueue()复杂度为 O(n)
- dequeue()复杂度为 O(1)

### 双端队列 
- addFront/removeFront    O(1)
- addRear/removeRear   O(n)